package main

import (
	"fmt"
)

func structure(list []int) {

}

func backtraceStructure() {
	// 如果满足条件 添加到结果列表
	// 遍历可选项
	// 加入
	// backtraceStructure
	// 删除
}

// 22.括号生成 https://leetcode.cn/problems/generate-parentheses/
func generateParenthesis(n int) []string {
	generateParenthesisRes = nil
	generateParenthesisPath = nil
	generateParenthesisBacktrack(n, n, n)
	return generateParenthesisRes
}

var generateParenthesisRes []string
var generateParenthesisPath []byte

func generateParenthesisBacktrack(n int, leftAvailable, rightAvailable int) {
	if leftAvailable > rightAvailable {
		return //非法了
	}

	if leftAvailable < 0 || rightAvailable < 0 {
		return
	}

	if leftAvailable == 0 && rightAvailable == 0 {
		generateParenthesisRes = append(generateParenthesisRes, string(generateParenthesisPath))
		return
	}

	// 添加左括号
	l := len(generateParenthesisPath)
	generateParenthesisPath = append(generateParenthesisPath, '(')
	generateParenthesisBacktrack(n, leftAvailable-1, rightAvailable)
	generateParenthesisPath = generateParenthesisPath[:l:l] //出栈

	// 添加右括号
	generateParenthesisPath = append(generateParenthesisPath, ')')
	generateParenthesisBacktrack(n, leftAvailable, rightAvailable-1)
	generateParenthesisPath = generateParenthesisPath[:l:l] //出栈
}

// 39 组合总和 https://leetcode.cn/problems/combination-sum
func combinationSum(candidates []int, target int) [][]int {
	combinationSumRes = nil
	combinationSumPath = nil
	combinationSumVal = 0

	combinationSumBacktrack(candidates, 0, target)
	return combinationSumRes
}

var combinationSumRes [][]int
var combinationSumPath []int
var combinationSumVal int

func combinationSumBacktrack(candidates []int, start, target int) {
	if combinationSumVal > target {
		return
	}
	if combinationSumVal == target {
		tmpRes := make([]int, len(combinationSumPath))
		copy(tmpRes, combinationSumPath)
		combinationSumRes = append(combinationSumRes, tmpRes)
		return
	}
	for i := start; i < len(candidates); i++ {
		item := candidates[i]
		combinationSumPath = append(combinationSumPath, item)
		combinationSumVal += item

		combinationSumBacktrack(candidates, i, target)
		l := len(combinationSumPath) - 1
		combinationSumVal -= item
		combinationSumPath = combinationSumPath[:l:l]
	}
}

// 77 组合 https://leetcode.cn/problems/combinations
// combine77Backtrack 递归调用的时候参数错误了
func combine(n int, k int) [][]int {
	resCombine77 = nil
	combine77Backtrack([]int{}, 1, n, k)
	return resCombine77
}

var resCombine77 [][]int

func combine77Backtrack(path []int, start, n, k int) {
	if len(path) == k {
		tmpRes := make([]int, k)
		copy(tmpRes, path)
		resCombine77 = append(resCombine77, tmpRes)
		return
	}
	for i := start; i <= n; i++ {
		path = append(path, i)
		combine77Backtrack(path, i+1, n, k)
		pathNum := len(path) - 1
		path = path[:pathNum:pathNum]
	}
}

var numToChar = map[byte][]byte{
	'1': {},
	'2': {'a', 'b', 'c'},
	'3': {'d', 'e', 'f'},
	'4': {'g', 'h', 'i'},
	'5': {'j', 'k', 'l'},
	'6': {'m', 'n', 'o'},
	'7': {'p', 'q', 'r', 's'},
	'8': {'t', 'u', 'v'},
	'9': {'w', 'x', 'y', 'z'},
}

// 17. 电话号码的字母组合 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
func letterCombinations(digits string) []string {
	resLetterCombinations = nil
	dByte := []byte(digits)
	backtrack(dByte, []byte{}, 0)
	return resLetterCombinations
}

var resLetterCombinations []string

func backtrack(dByte []byte, combination []byte, dPos int) {
	if len(combination) == len(dByte) {
		if len(combination) != 0 {
			resLetterCombinations = append(resLetterCombinations, string(combination))
		}
		return
	}
	for i := dPos; i < len(dByte); i++ {
		charList := numToChar[dByte[i]]
		for _, c := range charList {
			combination = append(combination, c)
			backtrack(dByte, combination, i+1)
			num := len(combination) - 1
			combination = combination[:num:num]
		}
	}
}

func main_permute() {
	nums := []int{5, 4, 6, 2}
	v := permute(nums)
	fmt.Println(v)
}

func permute(nums []int) [][]int {
	permuteFinalRes = nil
	backtracePermute(nums, []int{}, map[int]bool{})
	return permuteFinalRes
}

var permuteFinalRes [][]int

func backtracePermute(nums []int, tmpRes []int, usedMap map[int]bool) {
	if len(tmpRes) == len(nums) {
		permuteFinalRes = append(permuteFinalRes, tmpRes)
		return
	}

	for _, v := range nums {
		if usedMap[v] {
			continue
		}
		usedMap[v] = true
		tmpRes = append(tmpRes, v)
		backtracePermute(nums, tmpRes, usedMap)
		delete(usedMap, v)

		// go 语言的坑
		size := len(tmpRes) - 1
		tmpRes = tmpRes[:size:size]
	}
}
